package com.solution;

/**
 * 23. 合并K个升序链表
 * 给你一个链表数组，每个链表都已经按升序排列。
 *
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 * 示例 1：
 *
 * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
 * 输出：[1,1,2,3,4,4,5,6]
 * 解释：链表数组如下：
 * [
 *   1->4->5,
 *   1->3->4,
 *   2->6
 * ]
 * 将它们合并到一个有序链表中得到。
 * 1->1->2->3->4->4->5->6
 * 示例 2：
 *
 * 输入：lists = []
 * 输出：[]
 * 示例 3：
 *
 * 输入：lists = [[]]
 * 输出：[]
 *
 * @author LiYongKui
 * @version 1.0
 * @date 2021/1/27 10:14
 */
public class Solution0023 {

    static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public static ListNode mergeKLists(ListNode[] lists) {
        if(lists.length <= 0){
            return null;
        }
        ListNode pre = new ListNode(0,lists[0]);

        for (int i = 1; i < lists.length; i++) {
            ListNode tmp = pre;
            ListNode l1 = pre.next;
            ListNode l2 = lists[i];
            while(l2 != null || l1 != null){
                if(l1 == null){
                    tmp.next = l2;
                    break;
                }
                if(l2 == null){
                    tmp.next = l1;
                    break;
                }

                if(l1.val >= l2.val){
                    tmp.next = l2;
                    l2 = l2.next;
                }else{
                    tmp.next = l1;
                    l1 = l1.next;
                }
                tmp = tmp.next;
            }
        }
        return pre.next;
    }

    public static void main(String[] args) {
//        ListNode[] lists = {
//                new ListNode(1,new ListNode(4,new ListNode(5))),
//                new ListNode(1,new ListNode(3,new ListNode(4))),
//                new ListNode(2,new ListNode(6))
//        };
        ListNode[] lists = {};
        ListNode result = mergeKLists(lists);
    }
}
